package chapter04_RecursionAndDynamic;

/**
 * 描述：
 *      最长公共子序列
 * @author hl
 * @date 2021/6/16 9:11
 */
public class Lcse {
    public static void main(String[] args) {
        String str1 = "1A2C3D4B56";
        String str2 = "B1D23CA45B6A";
        Lcse lcse = new Lcse();
        String res = lcse.lcse(str1, str2);
        System.out.println(res);
    }
    /**
     * str1的长度为M， str2的长度为N，构建一个M * N的二维矩阵dp，dp[i][j]表示str1[0...i-1]与str2[0...j-1]的公共子序列的长度
     * @param str1
     * @param str2
     * @return
     */
    public String lcse(String str1, String str2){
        if (str1 == null || str2 == null || str1.length() == 0 || str2.length() == 0) {
            return null;
        }
        int[][] dp = getDp1(str1, str2);
        int i = str1.length() - 1, j = str2.length() - 1;
        char[] chs = new char[dp[i][j]];
        int index = dp[i][j] - 1;
        while(index >= 0){
            if (i > 0 && dp[i][j] == dp[i - 1][j]) {
                i--;
            }else if (j > 0 && dp[i][j] == dp[i][j - 1]) {
                j--;
            }else{
                chs[index--] = str1.charAt(i);
                i--;
                j--;
            }
        }
        return new String(chs);
    }

    public int[][] getDp1(String str1, String str2){
        int m = str1.length();
        int n = str2.length();
        int[][] dp = new int[m][n];
        dp[0][0] = str1.charAt(0) == str2.charAt(0) ? 1 : 0;
        for (int i = 1; i < m; i++) {
            dp[i][0] = str1.charAt(i) == str2.charAt(0) || dp[i - 1][0] == 1 ? 1 : 0;
        }
        for (int j = 1; j < n; j++) {
            dp[0][j] = str1.charAt(0) == str2.charAt(j) || dp[0][j - 1] == 1 ? 1 : 0;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                if (str1.charAt(i) == str2.charAt(j)) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - 1] + 1);
                }
            }
        }
        return dp;
    }
}
